/*
https://leetcode-cn.com/problems/strange-printer/solution/qi-guai-de-da-yin-ji-by-leetcode-solutio-ogbu/
 */
public class Solution664 {
    public int strangePrinter(String s) {
        int[][] f=new int[s.length()][s.length()];
        for (int i=s.length()-1;i>=0;i--){
            f[i][i]=1;
            for (int j=i+1;j<s.length();j++){
                if (s.charAt(i)==s.charAt(j)){
                    f[i][j]=f[i][j-1];
                }else{
                    int min=Integer.MAX_VALUE;
                    for (int k=i;k<j;k++){
                        min=Math.min(min,f[i][k]+f[k+1][j]);
                    }
                    f[i][j]=min;
                }
            }
        }
        return f[0][s.length()-1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution664().strangePrinter("aaabbb"));
    }
}
